package com.pan.games.leecode;

import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.Setter;

import java.util.*;

/**
 * @author by panstark
 * @description
 * @notice
 * @date 2021/3/26
 */
public class playWithTree {


    /**
     * 中序遍历
     * @param root
     * @param numList
     * @return
     */
    public static List<Integer>  inorderTraversal(TreeNode root,List<Integer> numList){

        if(root==null){
            return numList;
        }

        inorderTraversal(root.left,numList);
        numList.add(root.val);
        inorderTraversal(root.right,numList);

        return numList;
    }

    /**
     * 前序遍历
     * @param root
     * @param numList
     * @return
     */
    public static List<Integer> preorderTraversal(TreeNode root,List<Integer> numList) {
        if(root==null){
            return numList;
        }
        numList.add(root.val);
        preorderTraversal(root.left,numList);
        preorderTraversal(root.right,numList);
        return numList;
    }

    /**
     * 后续遍历
     * @param root
     * @param numList
     * @return
     */
    public static List<Integer> postorderTraversal(TreeNode root,List<Integer> numList) {
        if(root==null){
            return numList;
        }
        postorderTraversal(root.left,numList);
        postorderTraversal(root.right,numList);
        numList.add(root.val);
        return numList;
    }

    /**
     * 获取当前层各种值的list
     * 获取孩子节点list
     * @param levelNode
     * @param childTreeNodes
     * @return
     */
    public static List<Integer> levelOrderChild(List<TreeNode> levelNode,List<TreeNode> childTreeNodes) {

        List<Integer> integers = new ArrayList<>();
        for (TreeNode treeNode : levelNode) {
            if(treeNode==null){
                continue;
            }
            TreeNode leftChild = treeNode.left;
            TreeNode rightChild = treeNode.right;
            if(leftChild!=null){
                childTreeNodes.add(leftChild);
            }
            if(rightChild!=null){
                childTreeNodes.add(rightChild);
            }
            integers.add(treeNode.val);
        }
        return integers;
    }

    public static void levelOrder(List<TreeNode> levelNode,List<List<Integer>> listList){

        if(levelNode==null||levelNode.size()==0){
            return ;
        }
        List<TreeNode> childTreeNode = new ArrayList<>();
        List<Integer> integers = levelOrderChild(levelNode,childTreeNode);
        listList.add(integers);
        levelOrder(childTreeNode,listList);
    }

    /**
     * 自己写的层序遍历
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> listList = new ArrayList<>();
        if(root==null){
            return listList;
        }
        List<TreeNode> treeNodes = new ArrayList<>();
        treeNodes.add(root);

        levelOrder(treeNodes, listList);

        return listList;
    }

    /**
     * 二叉树的层序遍历，用到了队列
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrderByQueue(TreeNode root) {

        List<List<Integer>> allLevelVal = new ArrayList<>();

        if(root==null){
            return allLevelVal;
        }
        Queue<TreeNode> treeNodeQueue = new LinkedList<>();
        treeNodeQueue.offer(root);

        while(!treeNodeQueue.isEmpty()){
            List<Integer> singlelevelval = new ArrayList<>();
            int size = treeNodeQueue.size();
            for (int i = 0; i <size ; i++) {
                TreeNode poll = treeNodeQueue.poll();
                if(poll==null){
                    continue;
                }
                if(poll.left!=null){
                    treeNodeQueue.offer(poll.left);
                }
                if(poll.right!=null){
                    treeNodeQueue.offer(poll.right);
                }
                singlelevelval.add(poll.val);
            }
            allLevelVal.add(singlelevelval);
        }
        return allLevelVal;
    }


    /**
     * 从右侧观看一个树的所有节点
     * @param root
     * @return
     */
    public List<TreeNode> getNodeSeeFromRight(TreeNode root){

        List<TreeNode> nodesSeeFromRight = new ArrayList<>();
        if(root==null){
            return null;
        }
        Queue<TreeNode> treeNodeQueue = new LinkedList<>();
        treeNodeQueue.offer(root);
        while(!treeNodeQueue.isEmpty()){
            int size = treeNodeQueue.size();
            for (int i = 0; i <size ; i++) {
                TreeNode node = treeNodeQueue.poll();
                if(i==size-1){
                    nodesSeeFromRight.add(node);
                }
                if(node.right!=null){
                    treeNodeQueue.offer(node.right);
                }else if(node.left!=null){
                    treeNodeQueue.offer(node.left);
                }
            }
        }
        return nodesSeeFromRight;
    }

    public ListNode deleteDuplicates(ListNode head) {
        List<Integer> listNodes = new ArrayList<>();
        ListNode temp = head;
        ListNode pre = head;
        while(temp!=null){
            if(listNodes.contains(temp.val)){
                pre.next=temp.next;
            }else{
                listNodes.add(temp.val);
                pre = temp;
            }
            temp = temp.next;
        }
        return head;
    }

    public ListNode deleteDuplicatesSortedArray(ListNode head) {

        ListNode temp = head;
        ListNode pre = head;
        while(temp!=null){
            if(pre.val==temp.val){
                pre.next=temp.next;
            }else{
                pre = temp;
            }
            temp = temp.next;
        }
        return head;
    }





    public static void main(String[] args) {
        List<Integer> numList = new ArrayList<>();
        List<List<Integer>> listList = new ArrayList<>();


    }


}



@Getter
@Setter
@AllArgsConstructor
@NoArgsConstructor
class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;

}
